`
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
`

// https://labuladong.online/algo/images/binary-tree-i/3.png

/**
 * // Definition for a _Node. 
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function (root) {
  // 主函数
  if (root == null) return null;
  // 遍历「三叉树」，连接相邻节点
  traverse(root.left, root.right);
  return root;

  // 三叉树遍历框架
  function traverse(node1, node2) {
    if (node1 == null || node2 == null) {
      return;
    }
    // *** 前序位置 ***
    // 将传入的两个节点穿起来
    node1.next = node2;

    // 连接相同父节点的两个子节点
    traverse(node1.left, node1.right);
    traverse(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    traverse(node1.right, node2.left);
  }
};